#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class Solution {
    public:
        vector<string> anagrams(vector<string> &strs) {
            map<string, vector<string> > myMap;
            vector<string> ans;
            for (int i = 0; i < strs.size(); i++) {
                string str = strs[i];
                sort(str.begin(), str.end());
                if (myMap.count(str) != 0) {
                    myMap[str].push_back(strs[i]);
                } else {
                    myMap[str].push_back(strs[i]);
                }
             }
             for (map<string, vector<string> >::iterator iter = myMap.begin(); iter != myMap.end(); iter++) {
                 if (iter->second.size() > 1)
                    for (vector<string>::iterator iter1 = iter->second.begin(); iter1 != iter->second.end(); iter1++) 
                        ans.push_back(*iter1);
             }
             return ans;
        }
};

//add much better code
   vector<string> anagrams(vector<string> &strs) {
        vector<string> ans;
        map<string, vector<string> > mp; 
        for (int i = 0; i < strs.size(); i++) {
            string hash = strs[i];
            sort(hash.begin(), hash.end());
            if (mp.count(hash) == 0) {
                mp[hash].push_back(strs[i]);
            } else {
                if (mp[hash].size() == 1) ans.push_back(mp[hash][0]);
                mp[hash].push_back(strs[i]);
                ans.push_back(strs[i]);
            }   
        }   
        return ans; 
    }   


//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;
    string input[] = {"tea","and","ate","eat","den"};
    vector<string> strs;
    for (int i = 0; i < 5; i++) {
        strs.push_back(input[i]);    
    }
    vector<string> ans = mySolution.anagrams(strs);
    for (int i = 0; i < ans.size(); i++) 
        cout << ans[i] << " ";
    cout << endl;

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
